//实现 strStr() 函数。 
//
// 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如
//果不存在，则返回 -1 。 
//
// 
//
// 说明： 
//
// 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 
//
// 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 
//
// 
//
// 示例 1： 
//
// 
//输入：haystack = "hello", needle = "ll"
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：haystack = "aaaaa", needle = "bba"
//输出：-1
// 
//
// 示例 3： 
//
// 
//输入：haystack = "", needle = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= haystack.length, needle.length <= 10⁴ 
// haystack 和 needle 仅由小写英文字符组成 
// 
// 👍 1355 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        int[] next = new int[needle.length()];
        getNext(next,needle.toCharArray());
        //模式串起点
        int j = 0;
        char[] stack = haystack.toCharArray();
        char[] needleArray = needle.toCharArray();
        for (int i = 0;i<stack.length;i++){
            while (j>0&&stack[i]!=needleArray[j]){
                j = next[j-1];
            }
            if(stack[i]==needleArray[j]){
                j++;
            }
            if(j==needle.length()){
                return i-needle.length()+1;
            }
        }
        return -1;
    }
    public static void getNext(int[] next, char[] needle){
        //j代表前缀末尾
        int j = 0;
        //初始化赋值
        next[0] = 0;
        //i代表后缀末尾
        for (int i = 1; i<needle.length;i++){
            //如果不匹配 连续回滚
            while (j>0&&needle[i]!=needle[j]){
                j = next[j-1];
            }
            if(needle[i]==needle[j]){
                j++;
            }
            //将前缀末尾（前缀长度）赋给next[i]
            next[i] = j;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
